//
// Created by dengspc on 2019/2/13.
//

/*
 * DAG: directed Acycli Graph ,有向无环图
 * 强连通性:顶点 v 与 w是强连通的，则称为 v 与 w是强连通的
 * 在DAG中，任意两节点是强连通的，则称为有向图是强连通的。
 *
 * 当且仅当两个顶点在普通环中，才是强连通的。
 *自反性 传递性 对称性
 * 强连通分量：  DAG中相互强连通的的顶点的最大子集
 *
 *
 */

#ifndef INC_010_ALGORITHM_DIGRAPH_H
#define INC_010_ALGORITHM_DIGRAPH_H

#include <ostream>
#include <vector>
#include <stack>
#include <queue>
using namespace std;

class DiGraph {
public:
    virtual int V() = 0;//求顶点数量
    virtual int E() = 0;//求边数量
    virtual void addEdge(int v, int w) = 0;//向图中添加一条边 v w
    virtual vector<int>* adj(int v) = 0;//与v相邻的顶点集合
    virtual void print() = 0;//打印
    virtual int numOfSelfLoops() = 0 ;//计算自环的个数
    virtual DiGraph* reverse() = 0;//反转图


    /**
     * 计算v的度数
     * @param G
     * @param v
     */
    int degree(int v) {
        vector<int>* valList = adj(v);
        int size =  valList->size();
        delete valList;
        return size;
    }

    /**
     * 计算G的最大度数
     * @param G
     * @return
     */
    int maxDegree() {
        int max = 0;
        for (int i = 0; i < V(); i++) {
            int idegree = degree(i);
            max = idegree > max ? idegree : max;
        }
        return max;
    }

    /**
    * 求平均度数
    * @param G
    * @return
    */
    double avgDegree() {
        return (double)E() / V();
    }


};


/**
 * 图处理算法
 */
class DirectedDFS{
public:
    virtual bool marked(int v) = 0;//v 与 source 是否连通
};

/**
 * 图路径算法
 */
class DirectedPaths{
protected:
    bool* marks;//标记对应点是否被访问过 true = 访问过
    int* edges;//边集合，类似18-uf工程中的并查集，不断递归，最终指向source edges[?] = source。总体来说存储路径
    int source;//目标顶点
public:
    bool hasPathTo(int v){
        return marks[v];
    }//v 与 source 是否存在路径
    stack<int>* pathTo(int v) {
        if(!hasPathTo(v)) return NULL;
        stack<int>* stack1 = new stack<int>();
        for(int x = v; x != source; x = edges[x]){
            stack1->push(x);
        }
        stack1->push(source);
        return stack1;

    } // 与 source 与v 的路径

};

/**
 * 图存在环？（
 */
class DirectedCycle{
public:
    virtual bool hasCycle() = 0;//是否存在环
    virtual stack<int>* cycle() = 0;//环的路径
};

/**
 * 顺序定义
 */
class DirectedOrder{
public:
    virtual queue<int>* pre() = 0;//递归的前序
    virtual queue<int>* post() = 0;//递归的后序
    virtual stack<int>* reversePost() = 0;//递归的逆后序
};


/**
 * 拓扑排序API
 * 当且仅当一副有向图无环才可拓扑排序
 * 定义：给定一幅有向图，将所有的顶点排序，使得所有的边都从排在前面的元素指向排在后面的元素
 */
class Topological{
public:
    virtual bool isDAG() = 0;// 是有向无环图吗
    virtual queue<int>* order() = 0;// 拓扑有序的所有顶点
};

/**
 * 图强连通分量
 *
 * kosaraju 科萨拉朱 算法（强连通分量计算算法）
 */
class KosarajuSCC{
public:
    virtual bool strongConnected(int v, int w) = 0;//v 与 w 是否连通
    virtual int count() = 0; // 连通分量数
    virtual int id(int v) = 0; // v所在连通分量的顶点(标识符)
};


#endif //INC_010_ALGORITHM_GRAPH_H
